// https://leetcode.cn/problems/zigzag-conversion/

// 算法思路总结：
// 1. 使用字符串数组模拟Z字形排列
// 2. 按顺序遍历字符，控制行索引上下移动
// 3. 到达首尾行时改变移动方向
// 4. 最后按行拼接所有字符串
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <string>
#include <vector>

class Solution 
{
public:
    string convert(string s, int numRows) 
    {
        if (numRows == 1) return s;

        int i = 0, flag = -1;
        int n = s.size();
        vector<string> rows(numRows);

        for (char& ch : s)
        {
            rows[i].push_back(ch);

            if (i == 0 || i == numRows - 1)
                flag = -flag;     
            i += flag;
        }

        string res;
        for (string& str : rows)
            res += str;

        return res;
    }
};

int main()
{
    string s1 = "PAYPALISHIRING", s2 = "PAYPALISHIRING";
    int n1 = 3, n2 = 4;
    
    Solution sol;
    cout << sol.convert(s1, n1) << endl;
    cout << sol.convert(s2, n2) << endl;

    return 0;
}